118. 杨辉三角
#leetcode#动态规划 2025-01-31

Problem: 118. 杨辉三角

解析

利用杨辉三角特性，每一行的第一个和最后一个元素都是1，中间元素等于上一行的前一个元素和当前元素之和。

朴素动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//! n^2,n -> 这里的空间复杂度不管返回值的占用空间
class Solution {
 public:
  vector<vector<int>> generate(int numRows) {
    vector<vector<int>> res;
    vector<int> resPart;
    vector<int> DP(numRows);
    DP[0] = 1;
    vector<int> temp;
    for (int i = 0; i < numRows; ++i) {
      resPart.push_back(1);
      temp = DP;
      for (int j = 1; j <= i; ++j) {
        temp[j] = DP[j - 1] + DP[j];
        resPart.push_back(temp[j]);
      }
      DP = temp;
      res.push_back(resPart);
      resPart.clear();
    }
    return res;
  }
};

简化

可去掉中间的暂存值简化代码为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//! n^2,n
class Solution {
 public:
  vector<vector<int>> generate(int numRows) {
    vector<vector<int>> res;
    for (int i = 0; i < numRows; ++i) {
      vector<int> temp(i + 1, 1);  // 每行初始化为1
      for (int j = 1; j < i; ++j) {
        temp[j] = res[i - 1][j - 1] + res[i - 1][j];
      }
      res.push_back(temp);
    }
    return res;
  }
};

进一步优化

甚至可以开始给res numRows的空间，用res[i].resize(i+1)把中间的temp数组去掉，懒得搞了